package NiuKe;

public class Dynamic_Planning {
    public static void main(String[] args){
        int[] arrty = {1,-2,3,10,-4,7,2,-5};
        System.out.println(FindGreatestSumOfSubArray(arrty));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        // 如果数组只有一个元素，直接返回该元素的值
        if(array.length == 1){
            return array[0];
        }

        // 创建一个dp数组，用于保存中间计算的结果
        int[] dp = new int[array.length];
        dp[0] = array[0]; // 初始化dp数组的第一个元素为数组的第一个元素
        int ans = array[0]; // 初始化最大和的结果为数组的第一个元素

        // 遍历数组的剩余元素，计算每个子问题的最优解，并更新最大和的结果
        for(int i = 1; i < array.length; i++){
            // dp[i]的值为当前元素与前一个元素的最大连续和
            // 如果前一个子数组的最大和加上当前元素的值大于当前元素本身的值，
            // 则说明当前元素可以与前面的连续子数组构成更大的和
            // 否则，当前元素自成一个新的连续子数组
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);

            // 更新最大和的结果
            ans = Math.max(ans, dp[i]);
        }

        // 返回最大和的结果作为最终答案
        return ans;
    }
}
